/**
 * 猫构造函数
 * @param {Number} id 主键id
 * @param {String} name 名字
 */
function Cat(id, name) {
	this.id = id;
	this.name = name;
}

/**
 * 顺序查找id符合条件的实例在列表中位置
 * @param {Array<Cat>} catList 列表
 * @param {Number} id id
 * @returns 符合条件的实例位置，未找到返回-1
 */
function search(catList, id) {
	for (let i = 0; i < catList.length; i++) {
		if (catList[i].id === id) {
			return i;
		}
	}
	return -1;
}

/**
 * 折半查找id符合条件的实例在列表中位置
 * @param {Array<Cat>} catList 列表
 * @param {Number} id id
 * @returns 符合条件元素位置，未找到返回-1
 */
function binarySearch(catList, id) {
	// 初始化上下界下标（指针）
	let low = 0;
	let high = catList.length - 1;
	let mid;
	while (low <= high) {
		// 向下取整
		mid = Math.floor((low + high) / 2);
		// 若查找到元素则返回其位置
		if (catList[mid].id === id) {
			return mid;
		} else if (id > catList[mid].id) {
			// 否则，如果待查找元素的id比mid处的大，则将范围规定到后半部分
			low = mid + 1;
		} else {
			// 否则，在前半部分查找
			high = mid - 1;
		}
	}
	return -1;
}

// 测试
let catList = [];
for (let i = 0; i < 1000000; i++) {
	catList.push(new Cat((Math.pow(i, 2) + i + 1), '猫'));
}
// 顺序查找
let start = new Date();
console.log('顺序查找结果：' + search(catList, 980100990001));
let end = new Date();
console.log('顺序查找用时：' + (end - start) + 'ms');
// 折半查找
start = new Date();
console.log('折半查找结果：' + binarySearch(catList, 980100990001));
end = new Date();
console.log('折半查找用时：' + (end - start) + 'ms');